Online Lectures on Bioinformatics
Suboptimal Alignments
Suboptimal points
Definicja:Dowolne dwie sekwencje z optymalnym alignmentem określono jako s. An
jest alignmentem pierwszego typu, którego wartość nie jest mniejsza niż
.
Każdy punkt na ścieżce wykresu pierwszego typu odpowiedniego dla takiego alingmentu jest nazywany
.
Miejsce wszystkich 
-suboptymalnych punktów
jest określane jako
.
Następujące proste obserwacje prowadzą do metod obliczania miejsc punktów suboptymalnych. Załóżmy, że a residue pair (reszty) znajdujące się wewnątrz alignment pierwszego typu są naprawione. Wartość wewnętrznego alignmentu jest sumą wartości par obecnych na jego lewym końcu oraz wartości reszty alignmentu nie obliczona waga par). Macierz L(i,j), która została zdefiniowana w rozdziale 2.2, zawiera dokładnie wartości alimentów od początku sekwencji do punktu macierzy. W obecnym kontekście musimy nazwać macierz jako L- ale wyliczyć ją zgodnie z tymi samymi zasadami jak poprzednio
Początkowe ustawienia zależą od tego czy końce przerw są karalne czy nie. Ogólnie L-(1,i) (L-(j,1)) stanowią w(1,i) (w(j,1)) i w ten sposób przerwy obecne na lewym końcu nie są karane.
Wynik postępowania alignmentu od punktu macierzy do końca może być obliczony przez odwrócenie the order of execution w powyższy algorytm (to odpowiada przedstawieniu podobnej procedurze na podwójnym wykresie pierwszego typu). W skutek tego macierz L+ jest obliczana przez:
Polecenie obliczenia jest wycofywane wzdłuż każdego rzędu od(|s|, |t|) musi być wykonana w podobny sposób jak dla wyliczenia L- , np.
and
.
Adding
L-(i,j) + L+(i,j) counts the score for the pair (i,j) twice.
Therefore the score of the best type I alignment going through (i,j)is
Dodanie
-suboptymalny punkt moze być przeliczony jako
(
)
Dla liniowych przerw, które są karalne funkcje wyliczenia L- i L+ mogą być przyspieszone przez stosowanie tego samego postępu jak w przypadku algorytmu A-II-l opisanego w rozdziale 2. Podobny algorytm do SOP został zaproponowany przez Sellers ([Sel79],[Sel80]) dla drugiego typu alignmentów i przez Boswell i McLachlan [BoM84] dla pierwszego typu alignmentów.
Łatwe jest zaobserwowanie, że maksymalna wartość założona
musi myć optymalną wartością algorytmu.
s
This value is assumed along all optimal alignments.
On the other hand, not every alignment that consists of points
in S0 is an optimal alignment
.
Neither is every alignment made up of points in
,
,
itself -suboptimal. This gives rise to the next
algorithm due to M. Waterman ([Wat83],[ByW84])
for finding all -suboptimal alignments.
Comments are very welcome.
luz@molgen.mpg.de